//
// Created by Shao Wenhan on 2021/6/23.
//

#ifndef BINARYINDEXEDTREE_BINARYINDEXEDTREE_H
#define BINARYINDEXEDTREE_BINARYINDEXEDTREE_H

#include <vector>
using namespace std;

/*
 * 0. for the invoker, index of array with size n is from 0 to n-1.
 * 1. the least significant bit of number i is i & -i,
 *    because i can be represented as a1b, where 1 is the least significant bit of number i, b is all zero,
 *    and -i is ~(a1b)+1 = ~a0~b+1 = ~a1b, so i & -i is a1b & ~a1b = 1b.
 *    below, the least significant bit of number i is lsb(i).
 * 2. for ease of presentation, inside the class, size of array is n+1, and index is from 1 to n.
 * 3. m_array[i] records the sum from i-lsb(i)+1 to i, inclusively.
 */

template <typename Type>
class BinaryIndexedTree
{
private:
    vector<Type> m_array;
public:
    explicit BinaryIndexedTree(int size): m_array(size+1){};
    void initialize();
    Type sumFromStartToIndex(int index) const;
    void changeValueOfIndex(int index, Type delta);
    Type valueOfIndex(int index) const;
    void scaleAllValues(double factor);
};

template<typename Type>
void BinaryIndexedTree<Type>::initialize() {
    fill(m_array.begin(), m_array.end(), 0);
}

template<typename Type>
Type BinaryIndexedTree<Type>::sumFromStartToIndex(int index) const
{
    int res = 0;
    index += 1;
    while(index)
    {
        res += m_array[index];
        index &= index-1;
    }
    return res;
}

template<typename Type>
void BinaryIndexedTree<Type>::changeValueOfIndex(int index, Type delta)
{
    index += 1;
    while(index < m_array.size())
    {
        m_array[index] += delta;
        index += (index & -index);
    }
}

template<typename Type>
Type BinaryIndexedTree<Type>::valueOfIndex(int index) const
{
    int endIndex = (index+1) & index;
    Type res = m_array[index+1];

    /*
     * assume that index+1 is a1k0, where k0 indicates k zeros, m_array[index+1] records the sum from ak01 to a1k0.
     * in order to obtain the value of index+1, it needs to subtract sum from ak01 to a1k0-1, i.e. ak01 to a0k1.
     *
     * index is a0k1, m_array[index] records the sum from a0k1 to a0k1,
     * after subtracting it, it still needs to subtract sum from ak01 to a0(k-1)10,
     *
     * index = index & index-1 = a0(k-1)10, m_array[index] records the sum from a0(k-2)101 to a0(k-1)10,
     * after subtracting it, it still needs to subtract sum from ak01 to a0(k-2)100,
     *
     * after n iterations, index = a0(k-n)1n0, m_array[index] records the sum from a0(k-n-1)1n01 to a0(k-n)1n0,
     * after subtracting it, it still needs to subtract sum from ak01 to a0(k-n-1)1(n+1)0
     *
     * when n is equal to k-1, it still needs to subtract sum from ak01 to a01(k-1)0,
     * index = a01(k-1)0, m_array[index] records the sum from ak01 to a01(k-1)0,
     * after subtracting it, it still needs to subtract 0.
     * when n is equal to k, index = a(k+1)0 and the progress should terminate. so endIndex = index+1 & index.
     */
    while(index > endIndex)
    {
        res -= m_array[index];
        index &= index-1;
    }
    return res;
}

template<typename Type>
void BinaryIndexedTree<Type>::scaleAllValues(double factor)
{
    for(int i = 1; i < m_array.size(); i++)
        m_array[i] *= factor;
}

#endif //BINARYINDEXEDTREE_BINARYINDEXEDTREE_H
